package lc20240616;

import lc20240526.ListNode;

/**
  * @description 链表排序
  * @author 不知名帅哥
  * @date 2024/6/16 23:39
  * @version 1.0
*/
public class SortedLinkedList {
    public static void main(String[] args) {
        ListNode head=new ListNode(3);
        head.next=new ListNode(5);
        ListNode node=head.next.next=new ListNode(4);
        node.next=new ListNode(2,new ListNode(1));
        SortedLinkedList s = new SortedLinkedList();
        ListNode listNode = s.sortList(head);
        while (listNode!=null){
            System.out.println(listNode.val);
            listNode=listNode.next;
        }

    }

    public ListNode sortList(ListNode head){
        //只有0个或者一个节点的情况，同时为了防止后面的空指针异常。
        if (head==null||head.next==null){
            return head;
        }
        //找到中间节点
        ListNode slow=head;
        ListNode fast=head;
        ListNode prev=null;
        //注意循环条件的判断，防止空指针。
        while (fast!=null&&fast.next!=null){
            prev=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        //断链
        prev.next=null;

        ListNode l1=sortList(head);
        ListNode l2=sortList(slow);
        return merge(l1,l2);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy=new ListNode(0);
        ListNode current=dummy;
        //遍历两个链表直到一个链表为空

        while (l1!=null&&l2!=null){
            if (l1.val<l2.val){
                current.next=l1;
                l1=l1.next;
                current=current.next;
            }else {
                current.next=l2;
                l2=l2.next;
                current=current.next;
            }
        }
        //如果一个完全合并但是另一个还有剩余,连接剩余的部分
        if (l1!=null){
            current.next=l1;
        }else if (l2!=null){
            current.next=l2;
        }
        return dummy.next;
    }
//    public ListNode sortList(ListNode node){
//        if (node == null || node.next == null)
//            return node;
//        //定义快慢指针，找到中点。当fast走到末尾，slow也就到中间了。
//        ListNode fast = node.next, slow = node;
//        while (fast != null && fast.next != null) {
//            slow = slow.next;
//            fast = fast.next.next;
//        }
//
//        //保存副本作为right
//        ListNode tmp = slow.next;
//        slow.next = null;
//
//        ListNode left = sortList(node);
//        ListNode right = sortList(tmp);
//
//        ListNode h = new ListNode(0);
//        ListNode res = h;
//
//        while (left != null && right != null) {
//            if (left.val < right.val) {
//                h.next = left;
//                left = left.next;
//            } else {
//                h.next = right;
//                right = right.next;
//            }
//            h = h.next;
//        }
//        h.next = left != null ? left : right;
//        return res.next;
//
//    }
}
